/VA02 by Steven Pietrobon 1 May 2009
/
/Four state Viterbi decoder. g0 = 1+D^2 and g1 = 1+D+D^2.
/
/Input data is entered via the EDUC-8 keypad and displayed on the EDUC-8 octal 
/display using port 0. The decoded bit, time index and symbol index are 
/displayed in AC. The decoded bit is shown in AC7 (most significant bit). Bits 
/AC7 to AC1 show the time index and bit AC0 shows the symbol index. Symbols are 
/input in the order R0 (AC0=0) followed by R1 (AC0=1).
/
/The initial value in AC is 92 = 01011100_2, corresponding to a time index of 
/-18 = 128-2*18. After the input of the first 36 symbols, AC6 to AC0 will be 0 
/and the first decoded bit will be in AC7. This is due to the decoder delay 
/being equal to 18=L+m where L=16 is the traceback depth and m=2 is the encoder 
/memory.
/
/The octal display shows the current contents of the time and symbol index. 
/Assuming that the display is in 737 format, the two right most digits shows
/the magnitude of the symbol, from 00 to 11 in octal (0 to 9 in decimal). The
/left most digit shows the sign of the symbol, either 0 for a positive value or 
/8 for a negative value (since the sign bit is located in the most significant
/bit of the symbol register).
/
/To enter data for the current time and symbol index, first enter 0 or 1 for 
/the sign bit followed by the magnitude of the symbol (any digit from 0 to 9).
/After entering the magnitude, the contents of the symbol will be updated and
/displayed. If you made a mistake, just re-enter the sign and magnitude.

/Once the displayed data is correct, press the ENTER key. The symbol index will
/increment and display the current contents for the symbol. Enter the next 
/symbol. When ENTER is pressed with AC0=1, the Viterbi algorithm will be 
/performed for the two symbols that were entered. This includes branch metric
/calculation, state metric calculation, and traceback.
/
/After a short while the symbol index will be 0 and the time index increments
/by one module 64 (together the time and symbol index increments by one modulo
/128). The current decoded bit is displayed in AC7 and the previously stored
/symbol for R0 is displayed. If the next symbol is the same as that displayed,
/you can press ENTER without having to enter the symbol.
/
/As you can see, the program fills the entire 256 byte memory of the EDUC-8! As 
/always, the indirect variables were tricky to handle. The traceback states 
/from the state with the mimimum metric which was difficult to squeeze in. I 
/could have started at a random state, but starting at the state with the 
/minimum state metric increases performance with the short traceback memory 
/used.
/
/The state metrics use modulo 256 arithmetic in their calculation. This avoids
/any need to renormalise the metrics to prevent overflow. This technique only
/works if the difference between the maximum and minimum state metric is less
/than 128. The formula for this difference is d = (m+1)*n*q where q is the 
/maximum symbol magnitude. We have n=2, m=2 and q=9 which gives d=54 < 128. My
/first Viterbi decoder that I built as part of my Masters degree in 1986-1987 
/used the same technique. This was a 64 state decoder with n*q = 15 (branch 
/metrics were calculated using a lookup table) and m=6, giving d=105 < 128.
/
/If your code sequence starts in the zero state, then you should initialise
/the register contents of table SM. SM[0]=000 with SM[1]=SM[2]=SM[3]=200 in 737 
/format (64 decimal) (address locations 030 to 033). If starting in an unknown 
/state, then the SM contents should be zero. The code below initialises the 
/table assuming we start in state zero.
/
/I would have like to have done an 8 state decoder, as the 8 path decisions for
/each time would have fitted nicely into an 8-bit byte. However, there was
/just not enough room. A future modification to EDUC-8 where we have a page 0 
/reference for indirect variables and other commonly used variables and 
/constants might possibly allow this. The traceback depth would need to 
/increase to L=20 to meet the required minimum rule-of-thumb length of 5*(m+1).

PLUS,       127
SIGN,       128
FOUR,       4                /2^m {m=2 = encoder memory}
MINUS4,     -4               /-2^m
MINUS2,     -2               /-n  {n=2 = code rate inverse}
MINUS3,     -3
THREE,      3                /2^n-1
TWO,        2
DEPTH,      15               /L-1 {L=16= traceback depth}
MINUS16,    -16              /-L

RXA,        A(RX)
SMA,        A(SM)
NSMA,       A(NSM)
PDA,        A(PD)

CTR,        VAR              /Input counter
I0,         VAR              /Input index
XD,         VAR=92           /Decoded bit/time index = -n*(L+m) mod 128
I1,         VAR              /Branch Metric index
WA,         VAR=PDA          /Path Decision Write Address
SM0AD,      VAR              /State Metric Address 0
SM1AD,      VAR              /State Metric Address 1
NSMAD,      VAR              /New State Metric Address
BMAD,       VAR              /Branch Metric Address
PM,         VAR              /Path Metric
PMD,        VAR              /Path Metric Difference
SM0I,       VAR=SMA          /State Metric Address 0 Initial
NSMI,       VAR=NSMA         /New State Metric Address Initial
STATE,      VAR              /Traceback state
MSM,        VAR=0            /Minimum State Metric
RA,         VAR              /Path Decision Read Address
STCTR,      VAR              /State Counter
RACTR,      VAR              /Read Address Counter
XDHAT,      VAR              /Decoded data
INVRX,      VAR              /Invert sign bit of RX[0]

/0
BM,         ARRAY[4]         /Branch Metrics, must start in address 0
PD,         ARRAY[16]        /Path Decisions
/1
NSM,        ARRAY[4]         /New State Metrics
SM,         TABLE[4]         /State Metrics
            0                /Starting in state 0 initialisation
            64
            64
            64

START,      CLA.IAC
            CMA
            DCA CTR          /CTR := -2
/2
            TAD RXA
            DCA I0           /I0 := A(RX)
            JMP WRITECHAR

NEXTCHAR,   RAR
            DCA I I0         /R[I0] := 128*AC
            JMS READCHAR
            TAD I I0 
            DCA I I0         /R[I0] := R[I0]+AC
WRITECHAR,  TAD I I0         /AC := R[I0]
            LDS 0            /write(AC)
            JMS READCHAR
            SMA              /if AC >= 0
            JMP NEXTCHAR     /then NEXTCHAR else
/3
            INC I0           /I0 := I0+1
            ISZ XD           /XD := XD+1, if XD <> 0
            CLA              /then AC := 0 else
            CLA              /AC := 0
            ISZ CTR          /if CTR < 0
            JMP WRITECHAR    /then WRITECHAR else
BMC,        DCA I1           /I1 := A(BM) = 0, Branch Metric Calculator
            DCA INVRX        /INVRX := 0
            JMP PAGE4
/4
PAGE4,      JMS MAKEBM       /Make BM[0]
            JMS MAKEBM       /Make BM[1]
            DCA INVRX        /INVRX := 128
            JMS MAKEBM       /Make BM[2]
            JMS MAKEBM       /Make BM[3], AC=128
SMC,        CMA              /State Metric Calculator
            TAD MSM
            DCA MSM          /MSM := MSM+127
            TAD SM0I
            DCA SM1AD        /SM1AD := SM0I
            TAD SM0I
/5
            DCA SM0AD        /SM0AD := SM0I
            TAD NSMI
            DCA NSMAD        /NSMAD := NSMI
            DCA I WA         /PD[WA] := 0
            JMP FIRSTSM

MSMCONT,    TAD I WA
            RAL
            DCA I WA         /PD[WA] := 2*PD[WA] + (PMD div 128)
            JMP I MAKESM
MAKESM,     RTNADR
            TAD I SM0AD
/6
            TAD I BMAD
            DCA PM           /PM := SM[SM0AD] + BM[BMAD]
            TAD BMAD
            CMA.IAC
            TAD THREE
            DCA BMAD         /BMAD := 2*BM(A)+3-BMAD = 3-BMAD
            TAD PM
            CMA.IAC
            TAD I BMAD
            TAD I SM1AD
            JMP PAGE7
/7
RX,         ARRAY[2]         /Received Data

PAGE7,      DCA PMD          /PMD := SM[SM1AD] + BM[BMAD] - PM
            TAD PMD
            SMA              /if PMD < 0
            CLA
            TAD PM           /then NSM[NSMAD] := PMD + PM
            DCA I NSMAD      /else NSM[NSMAD] := PM
FINDMSM,    TAD MSM
            CMA.IAC
            TAD I NSMAD      /AC := NSM[NSMAD]-MSM
            SMA              /if AC >= 0
/8
            JMP NEWPM        /then NEWPM else
            TAD MSM          
            DCA MSM          /MSM := AC+MSM = NSM[NSMAD]
            TAD NSMAD
            DCA STATE        /STATE := NSMAD
NEWPM,      CLA
            INC NSMAD        /NSMAD := NSMAD+1
            TAD PMD
            AND SIGN
            JMP MSMCONT
/9
FIRSTSM,    INC SM1AD
            INC SM1AD        /SM1AD := SM1AD+2
            DCA BMAD         /BMAD := BM(A) = 0
            JMS MAKESM
            JMS MAKESM
            INC SM0AD        /SM0AD := SM0AD+1
            INC SM1AD        /SM1AD := SM1AD+1
            INC BMAD         /BMAD := BMAD+1
            JMS MAKESM
            JMS MAKESM
TRACEBACK,  TAD MINUS16
/10
            DCA RACTR        /RACTR := -L = -16
            JMP DOTB

INCWA,      TAD WA
            TAD MINUS3       /AC := WA+1-A(PD) = WA-3
            AND DEPTH
            TAD PDA
            DCA WA           /WA := A(PD) + ((WA+1-A(PD)) mod 16)
DOTB,       NOP              /Replace with HLT 721 to debug traceback
            TAD WA
            DCA RA
/11
            TAD THREE        /AC := 3
            AND STATE
            DCA STATE        /STATE := STATE mod 4
            TAD STATE
            TAD MINUS4
            DCA STCTR        /STCTR := STATE-4
            TAD I RA         /AC := PD[RA]
READBIT,    RAR              /AC := RAR(AC)
            ISZ STCTR        /if STCTR <> 0
            JMP READBIT      /then READBIT else
/12
            AND SIGN
            DCA XDHAT        /XDHAT := AC and SIGN
MAKEXD,     TAD XD
            AND PLUS
            TAD XDHAT
            DCA XD           /XD := XDHAT + (XD mod 128)
NEXTSTATE,  TAD XDHAT        
            SZA              /if XDHAT <> 0
            TAD FOUR         /then AC := 4 else AC := 0
            JMP PAGE13
/13
PAGE13,     TAD STATE
            RAR
            DCA STATE        /STATE := (AC+STATE) div 2
            ISZ RACTR
            JMP INCWA
SWAP,       TAD NSMI
            DCA RACTR        /RACTR := NSMI
            TAD SM0I
            DCA NSMI         /NSMI := SM0I
            TAD RACTR
            DCA SM0I         /SM0I := RACTR
/14
            JMP START

READCHAR,   RTNADR
            TAD XD           /AC := XD
TESTCHAR,   SKF 0            /if CHARFLAG = 0
            JMP TESTCHAR     /then TESTCHAR else
            KRB 0            /read(AC), FLAG := 0
            JMP I READCHAR

MBMRTN,     TAD SIGN         /AC := 128
            JMP I MAKEBM
MAKEBM,     RTNADR           /Make Branch Metric
            TAD RX[1]        /AC := AC+RX[1]
            SMA              /if AC >= 0
/15
            CLA              /then BM[I1] := 0
            DCA I I1         /else BM[I1] := RX[1]
            TAD RX
            TAD INVRX
            SMA              /if RX+INVRX >= 0
            CLA              /then AC := BM[I1]
            TAD I I1         /else AC := BM[I1]+RX[0]
            AND PLUS
            DCA I I1         /BM[I1] := AC and 127
            INC I1           /I1 := I1+1
            JMP MBMRTN
